from itertools import combinations
from typing import List

def calculate_prefix_sum(grid):
    rows, cols = len(grid), len(grid[0])
    prefix_sum = [[0] * (cols + 1) for _ in range(rows + 1)]
    for i in range(1, rows + 1):
        for j in range(1, cols + 1):
            prefix_sum[i][j] = grid[i - 1][j - 1] + prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1]
    return prefix_sum

def get_rectangle_sum(prefix_sum, x1, y1, x2, y2):
    return prefix_sum[x2 + 1][y2 + 1] - prefix_sum[x2 + 1][y1] - prefix_sum[x1][y2 + 1] + prefix_sum[x1][y1]

def isRectangleOverlap(rec1: List[int], rec2: List[int]) -> bool:
    return not (rec1[2] < rec2[0] or rec1[0] > rec2[2] or rec1[3] < rec2[1] or rec1[1] > rec2[3])

def rectangles_overlap(rect1, rect2):
    return isRectangleOverlap([rect1[0], rect1[1], rect1[2], rect1[3]],
                              [rect2[0], rect2[1], rect2[2], rect2[3]])

def is_disjoint(rect1, rect2, rect3):
    return (not rectangles_overlap(rect1, rect2) and
            not rectangles_overlap(rect1, rect3) and
            not rectangles_overlap(rect2, rect3))

def calculate_area(rectangles):
    total_area = 0
    for (x1, y1, x2, y2) in rectangles:
        total_area += (x2 - x1 + 1) * (y2 - y1 + 1)
    return total_area

def generate_all_possible_rectangles(grid):
    rows, cols = len(grid), len(grid[0])
    rectangles = []
    for x1 in range(rows):
        for y1 in range(cols):
            for x2 in range(x1, rows):
                for y2 in range(y1, cols):
                    if any(grid[i][j] == 1 for i in range(x1, x2 + 1) for j in range(y1, y2 + 1)):
                        rectangles.append((x1, y1, x2, y2))
    return rectangles

def filter_rectangles_with_ones_on_edges(grid, rectangles):
    valid_rectangles = []
    for (x1, y1, x2, y2) in rectangles:
        if (any(grid[x1][j] == 1 for j in range(y1, y2 + 1)) and
            any(grid[x2][j] == 1 for j in range(y1, y2 + 1)) and
            any(grid[i][y1] == 1 for i in range(x1, x2 + 1)) and
            any(grid[i][y2] == 1 for i in range(x1, x2 + 1))):
            valid_rectangles.append((x1, y1, x2, y2))
    return valid_rectangles

def min_area_sum(grid):
    prefix_sum = calculate_prefix_sum(grid)
    all_rectangles = generate_all_possible_rectangles(grid)
    valid_rectangles = filter_rectangles_with_ones_on_edges(grid, all_rectangles)
    total_ones = sum(row.count(1) for row in grid)

    min_area = float('inf')

    for i in range(len(valid_rectangles)):
        for j in range(i + 1, len(valid_rectangles)):
            rect1, rect2 = valid_rectangles[i], valid_rectangles[j]
            if rectangles_overlap(rect1, rect2):
                continue
            for k in range(j + 1, len(valid_rectangles)):
                rect3 = valid_rectangles[k]
                if is_disjoint(rect1, rect2, rect3):
                    covered_ones = (
                        get_rectangle_sum(prefix_sum, *rect1) +
                        get_rectangle_sum(prefix_sum, *rect2) +
                        get_rectangle_sum(prefix_sum, *rect3)
                    )
                    if covered_ones == total_ones:
                        area = calculate_area([rect1, rect2, rect3])
                        min_area = min(min_area, area)

    return min_area if min_area != float('inf') else -1

grid = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 1, 0, 1, 1, 0],
        [0, 0, 0, 1, 1, 0, 1, 0, 1, 1],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 0, 1, 0, 1, 0, 1, 1]]

print(min_area_sum(grid))  # Example output
